package _11_整理题目._9_高频题目;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/first-missing-positive/
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * 
 * 思路：
 * 1、一般思路：使用 hashset
 *      遍历一次数组，将所有数据依次放入 hashset
 *      从 1 开始遍历，判断是否在里面
 *      判断时复杂度为 0(1), 但是 空间复杂度 0(n), 不符合要求
 * 
 * 2、原地哈希 https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
 *      首先我们要找的数在 区间 [1, n+1] 左闭右闭中，第 n+1 个数不用找，是找不到前 n 个数要返回的
 *      我们可以首先遍历一遍数组，然后将对应的数据填充到对应的位置上去，
 *      比如 1 就填充到 nums[0] 的位置，2 就填充到 nums[1]，如果填充过程中，nums[i] < 1 && nums[i] > len，那么直接舍弃
 *       
 *      第二遍遍历数组，判读 nums[i] != i+1 的数 i+1 就是我们要找的
 * 
 */
public class _05_缺失的第一个正数 {
    
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            while(nums[i]>=1 && nums[i]<=n && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        
        for(int i=0; i<n; i++) {
            if(nums[i] != i+1) {
                return i+1;
            }
        }
        
        return n+1;
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    @Test
    public void main() {
        
    }
    
}
